package com.waitingresult.dfs;

import java.util.Scanner;

/**
 * 全排列
 */
public class DfsForCDemo {
    //N为根据题目给出的最大数据范围 n表示总共有几个位置
    public static int N = 10, n;
    //path数组记录走的每一个节点
    public static int[] path = new int[N];
    //用st数组记录1~n的数是否被使用过
    public static boolean[] st = new boolean[N];

    public static void main(String[] args) {
        //根据题目要求读入n的值
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        //调用dfs函数
        dfs(0);
    }
    public static void dfs(int u) {//u用来记录现在在第几层
        if (u == n) {//如果已经触底
            for (int i = 0; i < n; i++) {
                //按照题目要求输出结果，即path数组记录的节点内容
                System.out.print(path[i] + " ");
            }
            System.out.println();
            return;//函数调用结束
        }
        //没有触底的情况下
        for (int i = 1; i <= n; i++) {
            if (!st[i]) {//当数未被选用时
                path[u] = i;//记录当前节点
                st[i] = true;//将该数状态修改为已经使用
                dfs(u + 1);//继续搜索下一层
                //还原现场，即当函数调用结束（已经触底时）将该数状态修改为未被使用方便进行下一次搜索
                st[i] = false;
            }
        }
    }
}